CD Ware Multimedia 1995 May

home *** CD-ROM | disk | FTP | other *** search

/ CD Ware Multimedia 1995 May / cd Ware (Juegos) Epimundo.iso / DOS / C / MATV.ZIP / MATV.DOC < prev next >

Wrap

Text File | 1993-10-11 | 27.9 KB | 707 lines

Matv v1.0 An Simple Matrix Class Mark Von Tress, Ph.D. PO Box 171173 Arlington TX 76003 Compuserve User ID : 71530,1170 Date: October 10, 1993 You are responsible for what you do with the code. Here is a formal disclaimer: DISCLAIMER: THIS PROGRAM IS PROVIDED AS IS, WITHOUT ANY WARRANTY, EXPRESSED OR IMPLIED, INCLUDING BUT NOT LIMITED TO FITNESS FOR A PARTICULAR PURPOSE. THE AUTHOR DISCLAIMS ALL LIABILITY FOR DIRECT OR CONSEQUENTIAL DAMAGES RESULTING FROM USE OF THIS PROGRAM. Copyright (c) Mark Von Tress 1993 ----------- Matv v1.0 - A Simple Matrix Class: Page 3 --------- Table of Contents I. INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . 4 II. FINANCIAL CONDITIONS OF USE . . . . . . . . . . . . . . . 5 III. BASIC ALGORITHMS . . . . . . . . . . . . . . . . . . . . 5 A. The Vector Class . . . . . . . . . . . . . . . . . . 5 B. Vector Copy Constructor and Destructor . . . . . . . 7 C. Assignment . . . . . . . . . . . . . . . . . . . . . 8 E. Garbage(), PurgeVectors(), and SetupVectors() . . . . 10 F. Matrix Class . . . . . . . . . . . . . . . . . . . . 10 IV. FUNCTIONS . . . . . . . . . . . . . . . . . . . . . . . . 12 A. Unary Matrix Functions . . . . . . . . . . . . . . . 12 B. Patterned Matrices . . . . . . . . . . . . . . . . . 13 C. IO Functions . . . . . . . . . . . . . . . . . . . . 13 V. COMPILATION AND LIMITATIONS . . . . . . . . . . . . . . . 13 ----------- Matv v1.0 - A Simple Matrix Class: Page 4 --------- I. INTRODUCTION Matv is a simple matrix class. The program is a sketch of a redesign of my matrix program YAMP. Matv is useful in its own right though. I tend to like little add-in classes that easy to memorize. That way I can focus on the problem at hand rather than dig through documents for complicated details. I also think that this is a good property for a class to have given the number of downloads of some other simple classes like the BUMP matrix class by Clopper Almon, and STRPP, a string class by Carl Moreland. These are two popular small classes. YAMP tends to be on the complicated side of things, but in its defense, it is a more ambitious program. I also wanted to correct some of the design flaws I see in YAMP, and bring it more in line with current C++ styles. YAMP was my first C++ program, so I learned enough along the way to improve it. (YAMP v2.0 will probably be released in Winter of 94.) Hopefully Matv is more intuitive and portable. I have tested it in Borland C++ (DOS, Phar-Lap Dos Extender Lite, and Easywin), Visual C++ (DOS and QuickWin), Symantec C++ (DOS, DOSX, and Winc), and djgpp (DOS 32-bit protected mode). Matv is restricted to 64K matrices for the sake of DOS, but it is easily adapted to larger matrices in programs compiled with DOS extenders. Matv uses a method for passing matrices that I have not seen in most matrix classes. Most classes use reference counting to keep track of number of objects accessing a the matrix storage. The storage is deleted once the reference count goes to zero. This is a standard technique in strings. Reference counting for matrices is overkill since matrix storage need never be referenced more than twice during parameter passing. Reference counting also allows side effects due to multiple accesses to the matrix storage. Instead, Matv uses a "deletion responsibility" technique. Many matrices may point to the matrix storage (aliases), but only one may delete the storage. When a temporary matrix is about to be deleted by a function return, and the temporary is the returned object, then Matv lets you transfer the deletion responsibility of the matrix storage to the recieving copy. The copy constructor then may merely capture the storage base pointer, rather than allocate new storage and copy the data. I think of a trapeze act when I read the copy constructor. The trapeze is the matrix object and the Flying Walinda is the matrix storage. Think about it. ----------- Matv v1.0 - A Simple Matrix Class: Page 5 --------- II. FINANCIAL CONDITIONS OF USE If you like this program, send me $5.00 US (or buy a deserving beggar lunch. In either case, find a way to repay my charity.) You may distribute the package unchanged. I only plan to distribute it electronically. I retain the copyright as proof of authorship. III. BASIC ALGORITHMS A. The Vector Class Matv has two important classes: Vector and Matrix. The Vector is the public parent class of the Matrix class. The Vector class is responsible for memory allocation, and no math. The Matrix class is responsible for math, and is not responsible for memory allocation. The Vector class is set up to provide a consistant interface to memory managers. This way, you modify Vector, and not Matrix, when you want to change to different memory management strategies, such as virtual matrices, or 32 bit vectors. The Vector class is given by typedef enum bboolean { FFALSE, TTRUE } bboolean; class Vector { private : FLOAT *c; // vector of FLOATs int n; // number of FLOATs bboolean CanDelete; // Gives permission to delete c - // initially true bboolean CanAlias; // Can be aliased - initially true long signature; // for heap checking FLOAT *SetupVectors(int n); void PurgeVectors(void); public : Vector(void); Vector(int n); Vector(int n, FLOAT *x); Vector(Vector &a); Vector &operator = (Vector &a); ~ Vector(); FLOAT &operator() (int i); int rows(void) { return n; } static FLOAT Nrerror(const char *errormsg); void Garbage(const char *errormsg); ----------- Matv v1.0 - A Simple Matrix Class: Page 6 --------- friend ostream &operator << (ostream &s, Vector &v); void release() { if (CanAlias == TTRUE) CanDelete = FFALSE; } void CannotAlias() { CanAlias = FFALSE; } }; The class uses an enumerated type bboolean, which has values 0=FFALSE, and 1=TTRUE. There are so many boolean classes hidden in other libraries, I thought I would make one of my own to avoid any conflicts. Just use the first letter twice in the bboolean type. Also note "FLOAT" instead of "float". You may configure Matv for using double precision instead of floating points by defining the compiler directive USE_DOUBLES. The public part of Vector contains the elements of Coplien's standard canonical form: a default constructor, a copy constructor, a destructor, and an assignment operator. I also like to overload the insertion operator. Two extra constructors are provided. You can allocate a vector with n elements, and you can read an array of n FLOATs into a Vector. The function rows() returns the number of elements of the Vector, n, which is a private variable of the Vector. Elements are accessed through the function call operator(). The member functions, release() and CannotAlias() control the flow through the copy constructor, destructor, and assignment operator. The member Garbage() checks the integrity of the vector. If certian conditions are met, the vector has been corrupted, and the static member function Nrerror() is called to shut down the program. ----------- Matv v1.0 - A Simple Matrix Class: Page 7 --------- The private section of Vector contains the base pointer to the storage, c, the number of elements, n, the deletion responsibility, CanDelete, and whether or not the Vector can have an alias, CanAlias. The last two variables also control the flow mentioned above. B. Vector Copy Constructor and Destructor You have to study the copy constructor, destructor and assignment operator to understand how the variables CanDelete and CanAlias work. The function, release(), sets the deletion responsibility to FFALSE if the vector can have an alias. Note the first branch of the copy constructor. Vector::Vector(Vector &a) : n(a.n), CanDelete(TTRUE), CanAlias(TTRUE), signature(SIGNATURE) { if (a.CanDelete == FFALSE && a.CanAlias) { // a is not responsible for deleting c and a can have an //alias c = a.c; } else { c = SetupVectors(a.n); FLOAT *cc = c; FLOAT *acc = a.c; int i = n; while (i--) *cc++ = *acc++; } } If the vector to be copied is not responsible for deleting c, and it can have an alias, then the matrix being copied merely gets its storage by pointing to the storage in the vector reference a. The typical use of release is given in the code fragment Matrix f1( int n) { Matrix t=Fill(n,n,1); t.release(); return t; } Matrix x = f1(3); x = f1(4); In f1(), the deletion responsibility is released, and t can have ----------- Matv v1.0 - A Simple Matrix Class: Page 8 --------- an alias, so during the first branch of the copy constructor is used to pass the copy into x. This is faster and requires less storage than going through the second branch of the copy constructor. Note the copy constructor is also called before entering the assignment function, so the first branch of the copy constructor is also used for passing t to x. Look at the destructor. When t is destroyed because it is going out of scope, it is no longer responsible for deleting c, so c is not purged, but n is set to zero. When a vector has an n of zero, you are trying to access a deleted vector, so the program will stop if you call the member function Garbage(). Vector::~Vector() { n = 0; if (CanDelete == TTRUE) PurgeVectors(); } C. Assignment The assignment function must address the problem of aliased matrices. The problem arises when the incoming vector, a, was constructed via the first branch of copy constructor. First, the assignment operator checks for "a=a;" and returns directly. An alias is identified if the two vectors point to the same storage. When a is not responsible for deletion, then *this is given that responsibility, and assignment returns. When a is responsible for deleting c, then the alias is split by creating new storage for *this and copying the storage. In code, we have Vector &Vector::operator = (Vector &a) { if (this == &a) return *this; // deal with aliased storage if (c == a.c && a.CanDelete == FFALSE) { // *this is aliased with a, and a is not // responsible for deleting c. CanDelete = TTRUE; n = a.n; return *this; } if (c == a.c && a.CanDelete == TTRUE) { // *this is aliased with a, and a is // responsible for deleting c. c = SetupVectors(a.n); CanDelete = TTRUE; } ----------- Matv v1.0 - A Simple Matrix Class: Page 9 --------- // *this is no longer aliased with a if (n != a.n) { PurgeVectors(); c = SetupVectors(a.n); } FLOAT *cc = c; FLOAT *acc = a.c; int i = n; while (i--) *cc++ = *acc++; return *this; } Finally, if a and *this are not aliased, but have different lengths, then the storage for *this is reallocated, and the storage of a.c is copied into that of *this. D. Vector::CannotAlias(); There are conditions where a matrix should not have an alias. The member function CannotAlias() is provided to force the copy constructor through the second branch. The first case is when you want a matrix to be static. You might use a static matrix to accumulate results of a calculation between function calls: Matrix f2( Matrix &ref) { static Matrix accumulator = Fill(ref.r,ref.c,0); accumulator.CannotAlias(); accumulator = accumulator + ref; accumulator.release(); return accumulator; } The call of release() has no effect because of the call to CannotAlias(). The accumulated storage will be preserved across function calls. It would be corrupted if you called release() and not CannotAlias(). The second case is when a matrix is passed in as a reference and is also the return value that had its deletion responsibility released: ----------- Matv v1.0 - A Simple Matrix Class: Page 10 --------- Matrix f3( Matrix &ref ) { ref.release(); return ref; } void f4( Matrix &z ) { Matrix x = f3(z); } Note that the storage in z is deleted when x goes out of scope if z.CannotAlias() has not been called. (I actually made this mistake in one of the early incarnations of Matv.) E. Garbage(), PurgeVectors(), and SetupVectors() You should check the integrity of the matrices in the parameter list of a function call by calling Garbage. SetupVectors() allocates the storage for n+1 FLOATs. The value of c[0] is set to 0x5a5a, then the pointer c is incremented, so now c[-1] is 0x5a5a. The value of signature is also set to 0x5a5a. A vector is declared zero if signature does not equal 0x5a5a, or if c[-1] does not equal 0x5a5a. PurgeVectors increments signature and decrements the pointer c. Then c[0] is set to zero. Hence, Garbage() can tell from the heap if aliased storage has been deleted. It can also tell from the vector itself. F. Matrix Class The Matrix class is a public Vector. It is responsible for the mathematical operations. The declaration for the matrix is given by: class Matrix : public Vector { public : int r, c; FLOAT &operator() (int i, int j); Matrix(void) : Vector(1), r(1), c(1) { } Matrix(int rr, int cc) : Vector(rr*cc), r(rr), c(cc) { } Matrix(int rr, int cc, FLOAT *x) : Vector(rr*cc,x), r(rr), c(cc) { } Matrix(Matrix &a) : Vector(a), r(a.r), c(a.c) { } Matrix &operator = (Matrix &a); ~ Matrix() { } friend ostream &operator << (ostream &s, Matrix &m); ----------- Matv v1.0 - A Simple Matrix Class: Page 11 --------- void show(char *str); // list of arithmetic friend functions and compound // assignment operators. friend Matrix operator + (Matrix &a, Matrix &b); friend Matrix operator + (Matrix &a, FLOAT b); friend Matrix operator + (FLOAT b, Matrix &a); Matrix &operator += ( Matrix &a ); Matrix &operator += ( FLOAT b ); friend Matrix operator - (Matrix &a, Matrix &b); friend Matrix operator - (Matrix &a, FLOAT b); friend Matrix operator - (FLOAT b, Matrix &a); Matrix &operator -= ( Matrix &a ); Matrix &operator -= ( FLOAT b ); friend Matrix operator - (Matrix &a); // unary minus friend Matrix operator * (Matrix &a, Matrix &b); friend Matrix operator * (Matrix &a, FLOAT b); friend Matrix operator * (FLOAT b, Matrix &a); Matrix &operator *= ( Matrix &a ); Matrix &operator *= ( FLOAT b ); friend Matrix operator % (Matrix &a, Matrix &b); // emult friend Matrix operator % (FLOAT b, Matrix &a); friend Matrix operator % (Matrix &a, FLOAT b); Matrix &operator %= ( Matrix &a ); Matrix &operator %= ( FLOAT b ); friend Matrix operator / (Matrix &a, Matrix &b); friend Matrix operator / (Matrix &a, FLOAT b); friend Matrix operator / (FLOAT b, Matrix &a); Matrix &operator /= ( Matrix &a ); Matrix &operator /= ( FLOAT b ); }; Matrices are dimensioned from 1 to r rows, and 1 to c columns. (I know this is usually considered bad style to have r and c to be public, but I don't like to access r by rows() or c by cols(). It's 5 symbols to many for my taste, and I don't plan to change the indexing base from 1). Elements are indexed by the function call operator () instead of a double brackets implemented with a helper class. This is so that arrays of Matrix objects may be created. The array elements are accessed using brackets. Note that all of the constructors are just versions of the corresponding Vector constructors. All of the memory allocation ----------- Matv v1.0 - A Simple Matrix Class: Page 12 --------- happens in the constructor chain where the base class is initiallized first. The destructor also uses the base class destructor to handle the memory dealocation. The assignment operator just sets the values of r and c, and then calls the Vector assignment operator. Two display functions are offered. The insertion operator is overloaded, and there is a show function. You can say cout << "display string\n" << x; or x.show("display string") to display a matrix. The standard arithmetic operators are overloaded, and they commute with scalers. Also there is a elementwise multiplication operator denoted by "%", which has the same operator precidence as "*" and "/". You may also use the arithmetic compound assignment operators: +=, -=, *=, %=, and /=. The right hand sides may be matrices or scalers. IV. FUNCTIONS A. Unary Matrix Functions The unary matrix functions, are Tran(), Inv(), and Sweep(). These calculate the transpose of a matrix, and the inverse. The program stops if the matrix to be inverted is not square. The inverse is calculated using the g2sweep method. This is a modified Gaussian elimination. However, if the diagonal pivot is less than 1.0E-8, then that row and column are set to zero. The prototypes are given below. Matrix Tran(Matrix &a); // transpose Matrix Inv(Matrix &a); // invert - G2 sweep Matrix Sweep(int k1, int k2, Matrix &a); // g2 sweep The Sweep() function sweeps out columns k1 to k2. If k1 == 1 and k2 == a.r, then Sweep() returns the g2 generalized inverse. See matvtest.cpp for the use of Sweep() calculating regression coefficients. ----------- Matv v1.0 - A Simple Matrix Class: Page 13 --------- B. Patterned Matrices The patterned matrix functions are Fill(), Ident(), Submat(), Cv(), and Ch(). Fill() creates an r x cc matrix of constants, d. Ident() produces an n dimensional identity matrix. Submat() extracts a submatrix from a. The top left corner position in a is (lr,lc), and the bottom right corner position in a is (r,c). Cv() vertically concatenates two matrices with the same number of rows. Ch() horizontally concatentates two matrices with same number of columns. The prototypes of these functions are given below: Matrix Fill(int r, int cc, FLOAT d = 0); Matrix Ident(int n); Matrix Submat(Matrix &a, int lr, int lc, int r, int c); Matrix Cv( Matrix &a, Matrix &b ); // horizontal concatenation Matrix Ch( Matrix &a, Matrix &b ); // vertical concatentation C. IO Functions The ASCII file structure is now the same as YAMP. It has a title string on the first line that is no longer than 80 characters including a carriage return '\n'. The second line contains two integers. The first is the number of rows of the matrix, and the second is the number of columns. The remaining rows are rows of data. See catchv.dat for an example matrix. Reada() reads an ascii matrix from filename. Writea() writes matrix a to filename with the title line given by filetitle. The prototypes are given below. Matrix Reada(char *filename); void Writea(char *filename, Matrix &a, const char *filetitle = "A_Matrix"); V. COMPILATION AND LIMITATIONS Programs using Matv must follow some simple steps: 1. include matv.cpp in the project definition 2. include matv.h in each file that uses matrices. Compile and link the program. See matvtest.c for an example file using matv. Two compiler switches may be defined. NO_CHECKING is a speed-up option for finished programs. It disables calls to Garbage(), and ----------- Matv v1.0 - A Simple Matrix Class: Page 14 --------- range checking in the Matrix::operator()(int i, int j); function. USE_DOUBLES allows you to use double precision instead of floating point. Matv has some limitations. Matrices are limited to 64K for standard DOS programs. You can't get many more than 7 64K matrices in a 640k barrier machine, so this limitation is reasonable. The limitation can be changed if you have a DOS extender or a 32 bit compiler. You should change all the ints in the Vector class and code to unsigned longs. Then remove the size restriction in SetupVectors(). The technique above works well in djgpp, under Pharlap DOS extenders, and the the DOSX library in Symantec C++. You can also resort to huge pointers if you want matrices larger than 64K, but this is not very portable. Matv is not entirely portable, but it is much better than YAMP, and I was pleased with the results. IMHO, this will probably continue until compiler venders have had plenty of time to comply with the ANSI standard, which is not yet complete. C++ is a new and complex language. It works well in Borland C++ in the small, medium, compact, large, and huge DOS memory models. It also works in EasyWin. If you plan to use it in EasyWin, you should add a section of the code that calls kbhit() ever 200 or so times that Matrix::operator()(int i, int j); is called. This lets other applications get control of the system. The same statements holds for Visual C++, except you should issue a _wyeild() call in QuickWin applications instead of calls to kbhit(). Symantec C++ 6.0 accepted matv in the large memory model, but bombed on an allocation failure in the small memory model. I can't track it down, so you will have to use the large model until I figure this out. It also worked in the large memory model, but not the small, as a WinC application. I was unable to test it as a Win32s application because WinC has not yet been ported to Win32s. I hope Symantec decides to do this. It also failed to compile in the DOSX model. This is because Reada() calls istream::>>() to read doubles, but this function is not in the current DOSX library. Until Symantec fixes this problem, you need to replace Reada() with a function that calls fscanf() and standard C file functions for reading the data. You can cannibalize Reada() from YAMP to do this. The djgpp port also failed to compile Reada() and Writea() because the version I have uses the old streams library. You can cannibalize Reada() and Writea() from YAMP to get the fscanf() version. It works well otherwise. Using the modifications above, I was able to construct 500x500 matrices without problems. ----------- Matv v1.0 - A Simple Matrix Class: Page 15 --------- Remember, a 1000x1000 matrix of doubles takes 8 megs, so virtual memory is really necessary for big problems. The last limitation is the scope of the functions. I kept the list short to keep the program short. You can put in the functions you want. Also try translating some of my functions from YAMP, written in C++. They use similar methods. Anyway, Enjoy, and I hope you find this useful.